package com.laotang.第_14_章_贪心算法.字节面试题_小于n的最大数;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class NNumber {
    public static void main(String[] args) {
        int[] nums = {1,2,3,4,5,6,7,8,9};
        int n = 100;

        System.out.println(new NNumber().getMaxNum(nums, n));
    }

    int res = Integer.MAX_VALUE;
    public int getMaxNum(int[] nums, int n) {
        // 降序排列
        List<Integer> numsList = new ArrayList<>();
        for (int num : nums) numsList.add(num);
        Collections.sort(numsList, (i1, i2) -> i2 - i1);

        // 找到第一个小于 n 的整数，也就是最大值
        boolean isFound = dfs(numsList, String.valueOf(n), new ArrayList<>(), true);

        if (!isFound) {
            // 如果没找到的话，说明没有比 n 小的整数
            // 那么，返回少一位的最大值
            int len = String.valueOf(n).length();
            StringBuilder resNum = new StringBuilder();
            for (int i = 0; i < len - 1; i++) {
                resNum.append(numsList.get(0));
            }
            return Integer.parseInt(resNum.toString());
        }

        return res;
    }

    private boolean dfs(List<Integer> numsList, String nStr, List<Integer> list, boolean isEqual) {
        if (list.size() == nStr.length()) {
            StringBuilder total = new StringBuilder();
            for (int num : list) total.append(num);
            // 如果找到第一个小于 n 的数，直接终止递归
            if (Long.parseLong(total.toString()) < Integer.parseInt(nStr)) {
                res = Integer.parseInt(total.toString());
                return true;
            }
            return false;
        }

        for (int i = 0; i < numsList.size(); i++) {
            // 如果上一个数字相等的话，并且当前数字大于 n 对应的位的话，剪枝
            if (isEqual && numsList.get(i) > nStr.charAt(list.size()) - '0') continue;
            list.add(numsList.get(i));
            if (dfs(numsList, nStr, list, numsList.get(i) == nStr.charAt(list.size() - 1) - '0')) return true;
            list.remove(list.size() - 1);
        }
        return false;
    }
}
